package com.yanyeori.leetcode;

import lombok.Getter;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 面试经典 150 题 top-interview-150
 * https://leetcode.cn/studyplan/top-interview-150/
 *
 * @author chenkuan 2023/11/3
 */
public class TopInterview150 {
    /**
     * 88. 合并两个有序数组
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     *
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     * 解释：需要合并 [1,2,3] 和 [2,5,6] 。
     * 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
     *
     * 示例 2：
     *
     * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
     * 输出：[1]
     * 解释：需要合并 [1] 和 [] 。
     * 合并结果是 [1] 。
     *
     * 示例 3：
     *
     * 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
     * 输出：[1]
     * 解释：需要合并的数组是 [] 和 [1] 。
     * 合并结果是 [1] 。
     * 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
     *
     *
     *
     * 提示：
     *
     *     nums1.length == m + n
     *     nums2.length == n
     *     0 <= m, n <= 200
     *     1 <= m + n <= 200
     *     -109 <= nums1[i], nums2[j] <= 109
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        m--;
        n--;
        int total = nums1.length - 1;
        while (total >= 0 && n >= 0) {
            if (m < 0 || nums1[m] < nums2[n]) {
                nums1[total--] = nums2[n--];
            } else if (nums1[m] > nums2[n]) {
                nums1[total--] = nums1[m--];
            } else {
                nums1[total--] = nums1[m--];
                nums1[total--] = nums2[n--];
            }
        }
    }

    /**
     * 27. 移除元素
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     *
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     *
     *
     * 说明:
     *
     * 为什么返回数值是整数，但输出的答案是数组呢?
     *
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     *
     * 你可以想象内部操作如下:
     *
     * // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
     * int len = removeElement(nums, val);
     *
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [3,2,2,3], val = 3
     * 输出：2, nums = [2,2]
     * 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
     *
     * 示例 2：
     *
     * 输入：nums = [0,1,2,2,3,0,4,2], val = 2
     * 输出：5, nums = [0,1,4,0,3]
     * 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
     *
     *
     *
     * 提示：
     *
     *     0 <= nums.length <= 100
     *     0 <= nums[i] <= 50
     *     0 <= val <= 100
     */
    public int removeElement(int[] nums, int val) {
        int last = nums.length - 1;
        for (int i = last; i >= 0; i--) {
            if (nums[i] == val) {
                if (i != last) {
                    nums[i] = nums[last];
                }
                last--;
            }
        }
        return last + 1;
    }

    /**
     * 26. 删除有序数组中的重复项
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     *
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     *
     *     更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     *     返回 k 。
     *
     * 判题标准:
     *
     * 系统会用下面的代码来测试你的题解:
     *
     * int[] nums = [...]; // 输入数组
     * int[] expectedNums = [...]; // 长度正确的期望答案
     *
     * int k = removeDuplicates(nums); // 调用
     *
     * assert k == expectedNums.length;
     * for (int i = 0; i < k; i++) {
     *     assert nums[i] == expectedNums[i];
     * }
     *
     * 如果所有断言都通过，那么您的题解将被 通过。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,2]
     * 输出：2, nums = [1,2,_]
     * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
     *
     * 示例 2：
     *
     * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
     * 输出：5, nums = [0,1,2,3,4]
     * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 3 * 104
     *     -104 <= nums[i] <= 104
     *     nums 已按 非严格递增 排列
     */
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int i = 0, j = 1;
        x: for (; j < nums.length; i++) {
            if (nums[i] == nums[j]) {
                for (; ; j++) { //往后找不重复的第一个元素
                    if (j == nums.length - 1) { //已经是最后一位，直接跳出外层循环
                        break x;
                    }
                    if (nums[j] != nums[j + 1]) { //找到不同值，返回不同值的位置
                        j++;
                        break;
                    }
                }
                nums[i + 1] = nums[j]; //将后一个重复值替换为找到的不同值
            } else {
                j++;
            }
        }
        return i + 1;
    }

    /**
     * 169. 多数元素
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     *
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [3,2,3]
     * 输出：3
     *
     * 示例 2：
     *
     * 输入：nums = [2,2,1,1,1,2,2]
     * 输出：2
     *
     *
     * 提示：
     *
     *     n == nums.length
     *     1 <= n <= 5 * 104
     *     -109 <= nums[i] <= 109
     *
     *
     *
     * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
     */
    public int majorityElement(int[] nums) {
        //投票算法： 可以看成水果消消乐，但玩法是不同的水果两两消失。最后剩余的一定是超过半数的水果
        int winner = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (winner == nums[i]) {
                count++;
            } else if (count == 0) {
                winner = nums[i];
                count = 1;
            } else {
                count--;
            }
        }
        return winner;
    }

    /**
     * 121. 买卖股票的最佳时机
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     *
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     *
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[7,1,5,3,6,4]
     * 输出：5
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     *
     * 示例 2：
     *
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    public int maxProfit(int[] prices) {
        int buy = prices[0], money = 0;
        for (int i = 1; i < prices.length; i++) {
            buy = Math.min(buy, prices[i]);
            money = Math.max(money, prices[i] - buy);
        }
        return money;
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     *
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     *
     * 返回 你能获得的 最大 利润 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：prices = [7,1,5,3,6,4]
     * 输出：7
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     *      总利润为 4 + 3 = 7 。
     *
     * 示例 2：
     *
     * 输入：prices = [1,2,3,4,5]
     * 输出：4
     * 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     *      总利润为 4 。
     *
     * 示例 3：
     *
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
     *
     *
     *
     * 提示：
     *
     *     1 <= prices.length <= 3 * 104
     *     0 <= prices[i] <= 104
     */
    public int maxProfit1(int[] prices) {
        int buy = prices[0], money = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > buy) {
                money += prices[i] - buy;
            }
            buy = prices[i];
        }
        return money;
    }

    /**
     * 13. 罗马数字转整数
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
     *
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     *
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     *
     *     I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     *     X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     *     C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     *
     * 给定一个罗马数字，将其转换成整数。
     *
     *
     *
     * 示例 1:
     *
     * 输入: s = "III"
     * 输出: 3
     *
     * 示例 2:
     *
     * 输入: s = "IV"
     * 输出: 4
     *
     * 示例 3:
     *
     * 输入: s = "IX"
     * 输出: 9
     *
     * 示例 4:
     *
     * 输入: s = "LVIII"
     * 输出: 58
     * 解释: L = 50, V= 5, III = 3.
     *
     * 示例 5:
     *
     * 输入: s = "MCMXCIV"
     * 输出: 1994
     * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 15
     *     s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
     *     题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
     *     题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
     *     IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
     *     关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
     */
    public int romanToInt(String s) {
        int num = 0;
        for (int i = 0, length = s.length(); i < length; i++) {
            char c = s.charAt(i);
            char next = i != length - 1 ? s.charAt(i + 1) : ' ';
            switch (c) {
                case 'I':
                    if (next == 'V' || next == 'X') num--;else num++;
                    break;
                case 'V':
                    num += 5;
                    break;
                case 'X':
                    if (next == 'L' || next == 'C') num -= 10;else num += 10;
                    break;
                case 'L':
                    num += 50;
                    break;
                case 'C':
                    if (next == 'D' || next == 'M') num -= 100;else num += 100;
                    break;
                case 'D':
                    num += 500;
                    break;
                case 'M':
                    num += 1000;
                    break;
            }
        }
        return num;
    }

    /**
     * 58. 最后一个单词的长度
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
     *
     * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "Hello World"
     * 输出：5
     * 解释：最后一个单词是“World”，长度为5。
     *
     * 示例 2：
     *
     * 输入：s = "   fly me   to   the moon  "
     * 输出：4
     * 解释：最后一个单词是“moon”，长度为4。
     *
     * 示例 3：
     *
     * 输入：s = "luffy is still joyboy"
     * 输出：6
     * 解释：最后一个单词是长度为6的“joyboy”。
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 104
     *     s 仅有英文字母和空格 ' ' 组成
     *     s 中至少存在一个单词
     */
    public int lengthOfLastWord(String s) {
        int end = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                if (i < end) {
                    return end - i;
                }
            } else {
                end = Math.max(end, i);
            }
        }
        return end + 1;
    }

    /**
     * 14. 最长公共前缀
     * 简单
     * 相关标签
     * 相关企业
     *
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     *
     *
     * 示例 1：
     *
     * 输入：strs = ["flower","flow","flight"]
     * 输出："fl"
     *
     * 示例 2：
     *
     * 输入：strs = ["dog","racecar","car"]
     * 输出：""
     * 解释：输入不存在公共前缀。
     *
     *
     *
     * 提示：
     *
     *     1 <= strs.length <= 200
     *     0 <= strs[i].length <= 200
     *     strs[i] 仅由小写英文字母组成
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) return strs[0];
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (true) {
            char x = ' ';
            for (int j = 0, length = strs.length; j < length; j++) {
                String str = strs[j];
                if (str.length() == 0) return "";
                if (i == str.length()) return res.toString();
                if (j == 0) {
                    x = str.charAt(i);
                    continue;
                }
                if (x != str.charAt(i)) {
                    return res.toString();
                }
                if (j == length - 1) {
                    res.append(x);
                }
                if (str.length() == res.length()) {
                    return res.toString();
                }
            }
            i++;
        }
    }

    /**
     * 28. 找出字符串中第一个匹配项的下标
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：haystack = "sadbutsad", needle = "sad"
     * 输出：0
     * 解释："sad" 在下标 0 和 6 处匹配。
     * 第一个匹配项的下标是 0 ，所以返回 0 。
     *
     * 示例 2：
     *
     * 输入：haystack = "leetcode", needle = "leeto"
     * 输出：-1
     * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
     *
     *
     *
     * 提示：
     *
     *     1 <= haystack.length, needle.length <= 104
     *     haystack 和 needle 仅由小写英文字符组成
     */
    public int strStr(String haystack, String needle) {
        if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
        int start = -1, second = -1, n = 0, h = 0;
        char n1 = needle.charAt(0);
        while (true) {
            //needle找完，完全匹配，返回首字符位置start
            if (n == needle.length()) {
                return start;
            }
            //needle没找完，haystack找完了，返回-1
            if (h == haystack.length()) {
                return -1;
            }
            //首字符位置start 和 首字符出现的第二位置都没赋值，且haystack当前字符等于needle首字符，记录第二位置
            if (start != -1 && second == -1 && haystack.charAt(h) == n1) second = h;
            //匹配字符
            if (needle.charAt(n) == haystack.charAt(h)) {
                //如果是首字符匹配，则记录首字符位置start
                if (n == 0) start = h;
                //needle、haystack 指针都加1
                n++;
                h++;
            } else {
                //不匹配字符
                //第二位置（不匹配后下次开始的位置）已经大于haystack剩余匹配needle的长度，直接返回-1
                if (second > haystack.length() - needle.length()) return -1;
                if (n == 0 || second == -1) {
                    //needle的首字符与haystack当前字符不匹配，或者还没有已匹配的第二字符，则匹配haystack的下一个字符
                    h++;
                } else {
                    //haystack从第二字符second处开始匹配，second置为初始-1
                    h = second;
                    second = -1;
                }
                //不匹配的情况，置为初始
                n = 0;
                start = -1;
            }
        }
    }

    public int strStr1(String haystack, String needle) {
        if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            if (haystack.substring(i,  Math.min(i + needle.length(), haystack.length())).equals(needle)) return i;
        }
        return -1;
    }

    /**
     * 125. 验证回文串
     * 简单
     * 相关标签
     * 相关企业
     *
     * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
     *
     * 字母和数字都属于字母数字字符。
     *
     * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入: s = "A man, a plan, a canal: Panama"
     * 输出：true
     * 解释："amanaplanacanalpanama" 是回文串。
     *
     * 示例 2：
     *
     * 输入：s = "race a car"
     * 输出：false
     * 解释："raceacar" 不是回文串。
     *
     * 示例 3：
     *
     * 输入：s = " "
     * 输出：true
     * 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
     * 由于空字符串正着反着读都一样，所以是回文串。
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 2 * 105
     *     s 仅由可打印的 ASCII 字符组成
     */
    public boolean isPalindrome(String s) {
        if (s.length() < 2) return true;
        int start = 0, end = s.length() - 1;
        s = s.toLowerCase();
        while (start < end) {
            char s1 = s.charAt(start);
            char s2 = s.charAt(end);
            if (!Character.isLowerCase(s1) && !Character.isDigit(s1)) {
                start++;
                continue;
            }
            if (!Character.isLowerCase(s2) && !Character.isDigit(s2)) {
                end--;
                continue;
            }
            if (s1 != s2) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    /**
     * 392. 判断子序列
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     *
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     *
     * 进阶：
     *
     * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
     *
     * 致谢：
     *
     * 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "abc", t = "ahbgdc"
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：s = "axc", t = "ahbgdc"
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     0 <= s.length <= 100
     *     0 <= t.length <= 10^4
     *     两个字符串都只由小写字符组成。
     */
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        if (m == 0) return true;
        if (m > n) return false;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == m;
    }

    /**
     * 383. 赎金信
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     *
     * 如果可以，返回 true ；否则返回 false 。
     *
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *
     *
     *
     * 示例 1：
     *
     * 输入：ransomNote = "a", magazine = "b"
     * 输出：false
     *
     * 示例 2：
     *
     * 输入：ransomNote = "aa", magazine = "ab"
     * 输出：false
     *
     * 示例 3：
     *
     * 输入：ransomNote = "aa", magazine = "aab"
     * 输出：true
     *
     *
     *
     * 提示：
     *
     *     1 <= ransomNote.length, magazine.length <= 105
     *     ransomNote 和 magazine 由小写英文字母组成
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int m = ransomNote.length(), n = magazine.length();
        if (m == 0) return true;
        if (m > n) return false;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = magazine.charAt(i);
            int count = 1;
            if (map.containsKey(c)) count = map.get(c) + 1;
            map.put(c, count);
        }
        for (int i = 0; i < m; i++) {
            char c = ransomNote.charAt(i);
            if (!map.containsKey(c)) return false;
            Integer count = map.get(c);
            if (count == 0) return false;
            map.put(c, count - 1);
        }
        return true;
    }

    /**
     * 使用数组下标位置替代map
     */
    public boolean canConstruct1(String ransomNote, String magazine) {
        int m = ransomNote.length(), n = magazine.length();
        if (m == 0) return true;
        if (m > n) return false;
        int[] cnt = new int[26]; //最多26个字母
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) return false;
        }
        return true;
    }

    /**
     * 205. 同构字符串
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定两个字符串 s 和 t ，判断它们是否是同构的。
     *
     * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
     *
     * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
     *
     *
     *
     * 示例 1:
     *
     * 输入：s = "egg", t = "add"
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：s = "foo", t = "bar"
     * 输出：false
     *
     * 示例 3：
     *
     * 输入：s = "paper", t = "title"
     * 输出：true
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 5 * 104
     *     t.length == s.length
     *     s 和 t 由任意有效的 ASCII 字符组成
     */
    public boolean isIsomorphic(String s, String t) {
        int l = s.length();
        if (l <= 1) return true;
        int[] cnt1 = new int[128];
        int[] cnt2 = new int[128];
        for (int i = 0; i < l; i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (cnt1[c1] == 0 && cnt2[c2] == 0) {
                cnt1[c1] = c2 + 1;
                cnt2[c2] = c1 + 1;
            } else if (cnt1[c1] != c2 + 1 || cnt2[c2] != c1 + 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 290. 单词规律
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
     *
     * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
     *
     *
     *
     * 示例1:
     *
     * 输入: pattern = "abba", s = "dog cat cat dog"
     * 输出: true
     *
     * 示例 2:
     *
     * 输入:pattern = "abba", s = "dog cat cat fish"
     * 输出: false
     *
     * 示例 3:
     *
     * 输入: pattern = "aaaa", s = "dog cat cat dog"
     * 输出: false
     *
     *
     *
     * 提示:
     *
     *     1 <= pattern.length <= 300
     *     pattern 只包含小写英文字母
     *     1 <= s.length <= 3000
     *     s 只包含小写英文字母和 ' '
     *     s 不包含 任何前导或尾随对空格
     *     s 中每个单词都被 单个空格 分隔
     */
    public boolean wordPattern(String pattern, String s) {
        int i = 0, j = 0, m = pattern.length(), n = s.length();
        Map<Character, String> map1 = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();
        StringBuilder word = new StringBuilder();
        while (i < m && j < n) {
            char c1 = pattern.charAt(i);
            char c2 = s.charAt(j);
            if (c2 != ' ') word.append(c2);
            if (c2 == ' ' || j == n - 1) {
                if (!map1.containsKey(c1) && !map2.containsKey(word.toString())) {
                    map1.put(c1, word.toString());
                    map2.put(word.toString(), c1);
                } else if (!word.toString().equals(map1.get(c1)) || map2.get(word.toString()) != c1) {
                    return false;
                }
                word.delete(0, word.length());
                i++;
            }
            j++;
        }
        return i == m && j == n;
    }

    public boolean wordPattern1(String pattern, String s) {
        String[] array = s.split(" ");
        int i = 0, j = 0, m = pattern.length(), n = array.length;
        if (m != n) return false;
        Map<Character, String> map1 = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();
        while (i < m && j < n) {
            char c = pattern.charAt(i);
            String str = array[j];
            if (!map1.containsKey(c) && !map2.containsKey(str)) {
                map1.put(c, str);
                map2.put(str, c);
            } else if (!str.equals(map1.get(c)) || map2.get(str) != c) {
                return false;
            }
            i++;
            j++;
        }
        return i == m && j == n;
    }

    /**
     * 242. 有效的字母异位词
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     *
     * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
     *
     *
     *
     * 示例 1:
     *
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     *
     * 示例 2:
     *
     * 输入: s = "rat", t = "car"
     * 输出: false
     *
     *
     *
     * 提示:
     *
     *     1 <= s.length, t.length <= 5 * 104
     *     s 和 t 仅包含小写字母
     *
     *
     *
     * 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
     */
    public boolean isAnagram(String s, String t) {
        int m = s.length(), n = t.length();
        if (m != n) return false;
        int[] x = new int[128];
        for (int i = 0; i < m; i++) {
            x[s.charAt(i)]++;
            x[t.charAt(i)]--;
        }
        for (int i = 0; i < 128; i++) {
            if (x[i] != 0) return false;
        }
        return true;
    }

    /**
     * 进阶: 如果输入字符串包含 unicode 字符
     */
    public boolean isAnagram1(String s, String t) {
        int m = s.length(), n = t.length();
        if (m != n) return false;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            map.compute(s.charAt(i), (k, v) -> v == null ? 1 : v + 1);
            map.compute(t.charAt(i), (k, v) -> v == null ? -1 : v - 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) return false;
        }
        return true;
    }

    /**
     * 1. 两数之和
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     *
     * 示例 2：
     *
     * 输入：nums = [3,2,4], target = 6
     * 输出：[1,2]
     *
     * 示例 3：
     *
     * 输入：nums = [3,3], target = 6
     * 输出：[0,1]
     *
     *
     *
     * 提示：
     *
     *     2 <= nums.length <= 104
     *     -109 <= nums[i] <= 109
     *     -109 <= target <= 109
     *     只会存在一个有效答案
     *
     *
     *
     * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, m = nums.length; i < m; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return new int[0];
    }

    /**
     * 202. 快乐数
     * 简单
     * 相关标签
     * 相关企业
     *
     * 编写一个算法来判断一个数 n 是不是快乐数。
     *
     * 「快乐数」 定义为：
     *
     *     对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     *     然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     *     如果这个过程 结果为 1，那么这个数就是快乐数。
     *
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：n = 19
     * 输出：true
     * 解释：
     * 12 + 92 = 82
     * 82 + 22 = 68
     * 62 + 82 = 100
     * 12 + 02 + 02 = 1
     *
     * 示例 2：
     *
     * 输入：n = 2
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     1 <= n <= 231 - 1
     */
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            int total = 0;
            while (n > 0) {
                int d = n % 10;
                total += d * d;
                n = n / 10;
            }
            n = total;
        }
        return n == 1;
    }

    /**
     * 219. 存在重复元素 II
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,3,1], k = 3
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：nums = [1,0,1,1], k = 1
     * 输出：true
     *
     * 示例 3：
     *
     * 输入：nums = [1,2,3,1,2,3], k = 2
     * 输出：false
     *
     *
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 105
     *     -109 <= nums[i] <= 109
     *     0 <= k <= 105
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    /**
     * 228. 汇总区间
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个  无重复元素 的 有序 整数数组 nums 。
     *
     * 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
     *
     * 列表中的每个区间范围 [a,b] 应该按如下格式输出：
     *
     *     "a->b" ，如果 a != b
     *     "a" ，如果 a == b
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [0,1,2,4,5,7]
     * 输出：["0->2","4->5","7"]
     * 解释：区间范围是：
     * [0,2] --> "0->2"
     * [4,5] --> "4->5"
     * [7,7] --> "7"
     *
     * 示例 2：
     *
     * 输入：nums = [0,2,3,4,6,8,9]
     * 输出：["0","2->4","6","8->9"]
     * 解释：区间范围是：
     * [0,0] --> "0"
     * [2,4] --> "2->4"
     * [6,6] --> "6"
     * [8,9] --> "8->9"
     *
     *
     *
     * 提示：
     *
     *     0 <= nums.length <= 20
     *     -231 <= nums[i] <= 231 - 1
     *     nums 中的所有值都 互不相同
     *     nums 按升序排列
     */
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if (nums.length == 1) {
            list.add(String.valueOf(nums[0]));
            return list;
        }
        for (int i = 1, start = 0, length = nums.length; i < length; i++) {
            if (nums[i] - nums[i - 1] == 1) {
                if (i == length - 1) {
                    list.add(nums[start] + "->" + nums[i]);
                }
            } else {
                list.add(i - start > 1 ? nums[start] + "->" + nums[i - 1] : String.valueOf(nums[start]));
                if (i == length - 1) {
                    list.add(String.valueOf(nums[i]));
                }
                start = i;
            }
        }
        return list;
    }

    /**
     * 20. 有效的括号
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     *     左括号必须用相同类型的右括号闭合。
     *     左括号必须以正确的顺序闭合。
     *     每个右括号都有一个对应的相同类型的左括号。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "()"
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：s = "()[]{}"
     * 输出：true
     *
     * 示例 3：
     *
     * 输入：s = "(]"
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 104
     *     s 仅由括号 '()[]{}' 组成
     */
    public boolean isValid(String s) {
        if (s.length() <= 1) return false;
        Map<Character, Character> map = new HashMap<Character, Character>(){{
            put('(', ')');
            put('[', ']');
            put('{', '}');
        }};
        LinkedList<Character> list = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                list.addLast(c);
            } else if (list.size() == 0 || map.get(list.removeLast()) != c) {
                return false;
            }
        }
        return list.size() == 0;
    }

    /**
     * 141. 环形链表
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     *
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     *
     * 示例 2：
     *
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     *
     * 示例 3：
     *
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     *
     *
     *
     * 提示：
     *
     *     链表中节点的数目范围是 [0, 104]
     *     -105 <= Node.val <= 105
     *     pos 为 -1 或者链表中的一个 有效索引 。
     *
     *
     *
     * 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
     */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) return true;
            head = head.next;
        }
        return false;
    }

    @Getter
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
    }

    /**
     * 21. 合并两个有序链表
     * 简单
     * 相关标签
     * 相关企业
     *
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     *
     *
     * 示例 1：
     *
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     *
     * 示例 2：
     *
     * 输入：l1 = [], l2 = []
     * 输出：[]
     *
     * 示例 3：
     *
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     *
     *
     *
     * 提示：
     *
     *     两个链表的节点数目范围是 [0, 50]
     *     -100 <= Node.val <= 100
     *     l1 和 l2 均按 非递减顺序 排列
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) return null;
        ListNode head = null;
        ListNode next = null;
        while (list1 != null || list2 != null) {
            ListNode node;
            if (list1 == null) {
                node = new ListNode(list2.val);
                list2 = list2.next;
            } else if (list2 == null) {
                node = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                if (list1.val < list2.val) {
                    node = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    node = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            if (head == null) {
                head = node;
                next = node;
            } else {
                next.next = node;
                next = next.next;
            }
        }
        return head;
    }

    /**
     * 递归
     */
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

    /**
     * 2. 两数相加
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     *
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     *
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     *
     *
     * 示例 1：
     *
     * 输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：[7,0,8]
     * 解释：342 + 465 = 807.
     *
     * 示例 2：
     *
     * 输入：l1 = [0], l2 = [0]
     * 输出：[0]
     *
     * 示例 3：
     *
     * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     * 输出：[8,9,9,9,0,0,0,1]
     *
     *
     *
     * 提示：
     *
     *     每个链表中的节点数在范围 [1, 100] 内
     *     0 <= Node.val <= 9
     *     题目数据保证列表表示的数字不含前导零
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        ListNode head = null;
        ListNode next = null;
        int bit = 0;
        while (l1 != null || l2 != null) {
            ListNode node;
            if (l1 == null) {
                node = new ListNode(l2.val);
                l2 = l2.next;
            } else if (l2 == null) {
                node = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                node = new ListNode(l1.val + l2.val);
                l1 = l1.next;
                l2 = l2.next;
            }
            node.val = node.val + bit;
            bit = 0;
            if (node.val >= 10) {
                bit = node.val / 10;
                node.val = node.val % 10;
            }
            if (head == null) {
                head = node;
                next = node;
            } else {
                next.next = node;
                next = next.next;
            }
        }
        if (bit > 0) {
            next.next = new ListNode(bit);
        }
        return head;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 104. 二叉树的最大深度
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个二叉树 root ，返回其最大深度。
     *
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：3
     *
     * 示例 2：
     *
     * 输入：root = [1,null,2]
     * 输出：2
     *
     *
     *
     * 提示：
     *
     *     树中节点的数量在 [0, 104] 区间内。
     *     -100 <= Node.val <= 100
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    /**
     * 100. 相同的树
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     *
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     *
     *
     * 示例 1：
     *
     * 输入：p = [1,2,3], q = [1,2,3]
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：p = [1,2], q = [1,null,2]
     * 输出：false
     *
     * 示例 3：
     *
     * 输入：p = [1,2,1], q = [1,1,2]
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     两棵树上的节点数目都在范围 [0, 100] 内
     *     -104 <= Node.val <= 104
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /**
     * 226. 翻转二叉树
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [4,2,7,1,3,6,9]
     * 输出：[4,7,2,9,6,3,1]
     *
     * 示例 2：
     *
     * 输入：root = [2,1,3]
     * 输出：[2,3,1]
     *
     * 示例 3：
     *
     * 输入：root = []
     * 输出：[]
     *
     *
     *
     * 提示：
     *
     *     树中节点数目范围在 [0, 100] 内
     *     -100 <= Node.val <= 100
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }

    /**
     * 101. 对称二叉树
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：root = [1,2,2,null,3,null,3]
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     树中节点数目在范围 [1, 1000] 内
     *     -100 <= Node.val <= 100
     *
     *
     *
     * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
     */
    public boolean isSymmetric(TreeNode root) {
        //将右子树翻转，再对比左右子树是否相同
        return isSameTree(root.left, invertTree(root.right));
    }

    /**
     * 112. 路径总和
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     *
     * 叶子节点 是指没有子节点的节点。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
     * 输出：true
     * 解释：等于目标和的根节点到叶节点路径如上图所示。
     *
     * 示例 2：
     *
     * 输入：root = [1,2,3], targetSum = 5
     * 输出：false
     * 解释：树中存在两条根节点到叶子节点的路径：
     * (1 --> 2): 和为 3
     * (1 --> 3): 和为 4
     * 不存在 sum = 5 的根节点到叶子节点的路径。
     *
     * 示例 3：
     *
     * 输入：root = [], targetSum = 0
     * 输出：false
     * 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
     *
     *
     *
     * 提示：
     *
     *     树中节点的数目在范围 [0, 5000] 内
     *     -1000 <= Node.val <= 1000
     *     -1000 <= targetSum <= 1000
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        LinkedList<TreeNode> list = new LinkedList<>();
        int sum = root.val;
        while (true) {
            if (root.left != null && root.right != null) {
                root.val = sum;
                list.addLast(root);
            }
            if (root.left != null) {
                TreeNode left = root.left;
                root.left = null;
                sum += left.val;
                root = left;
            } else if (root.right != null) {
                sum += root.right.val;
                root = root.right;
            } else {
                if (sum == targetSum) return true;
                if (list.isEmpty()) return false;
                root = list.removeLast();
                sum = root.val;
            }
        }
    }

    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == targetSum;
        return hasPathSum1(root.left, targetSum - root.val) || hasPathSum1(root.right, targetSum - root.val);
    }

    /**
     * 222. 完全二叉树的节点个数
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     *
     * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [1,2,3,4,5,6]
     * 输出：6
     *
     * 示例 2：
     *
     * 输入：root = []
     * 输出：0
     *
     * 示例 3：
     *
     * 输入：root = [1]
     * 输出：1
     *
     *
     *
     * 提示：
     *
     *     树中节点的数目范围是[0, 5 * 104]
     *     0 <= Node.val <= 5 * 104
     *     题目数据保证输入的树是 完全二叉树
     *
     *
     *
     * 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    /**
     * 637. 二叉树的层平均值
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[3.00000,14.50000,11.00000]
     * 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
     * 因此返回 [3, 14.5, 11] 。
     *
     * 示例 2:
     *
     * 输入：root = [3,9,20,15,7]
     * 输出：[3.00000,14.50000,11.00000]
     *
     *
     *
     * 提示：
     *
     *     树中节点数量在 [1, 104] 范围内
     *     -231 <= Node.val <= 231 - 1
     */
    public List<Double> averageOfLevels(TreeNode root) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        countLevelValMap(root, map, 0);
        return map.values().stream()
                .map(x -> x.stream().mapToInt(Integer::intValue).average().orElse(0))
                .collect(Collectors.toList());
    }

    private void countLevelValMap(TreeNode root, Map<Integer, List<Integer>> map, int level) {
        if (root == null) return;
        map.computeIfAbsent(level, k -> new ArrayList<>()).add(root.val);
        countLevelValMap(root.left, map, level + 1);
        countLevelValMap(root.right, map, level + 1);
    }

    /**
     * 530. 二叉搜索树的最小绝对差
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     *
     * 差值是一个正数，其数值等于两值之差的绝对值。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [4,2,6,1,3]
     * 输出：1
     *
     * 示例 2：
     *
     * 输入：root = [1,0,48,null,null,12,49]
     * 输出：1
     *
     *
     *
     * 提示：
     *
     *     树中节点的数目范围是 [2, 104]
     *     0 <= Node.val <= 105
     */
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        List<Integer> list = new ArrayList<>();
        getSearchTreeSequence(root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size() - 1; i++) {
            min = Math.min(list.get(i + 1) - list.get(i), min);
        }
        return min;
    }

    /**
     * 获取查找二叉树的正序值列表
     */
    private void getSearchTreeSequence(TreeNode root, List<Integer> list) {
        if (root == null) return;
        getSearchTreeSequence(root.left, list);
        list.add(root.val);
        getSearchTreeSequence(root.right, list);
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [3,1,4,null,2], k = 1
     * 输出：1
     *
     * 示例 2：
     *
     * 输入：root = [5,3,6,2,4,null,null,1], k = 3
     * 输出：3
     *
     *
     *
     *
     *
     * 提示：
     *
     *     树中的节点数为 n 。
     *     1 <= k <= n <= 104
     *     0 <= Node.val <= 104
     *
     *
     *
     * 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
     */
    int count = 0, val = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return val;
        kthSmallest(root.left, k);
        count++;
        if (count == k) {
            val = root.val;
            return val;
        }
        kthSmallest(root.right, k);
        return val;
    }

    /**
     * 98. 验证二叉搜索树
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *
     * 有效 二叉搜索树定义如下：
     *
     *     节点的左子树只包含 小于 当前节点的数。
     *     节点的右子树只包含 大于 当前节点的数。
     *     所有左子树和右子树自身必须也是二叉搜索树。
     *
     *
     *
     * 示例 1：
     *
     * 输入：root = [2,1,3]
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：root = [5,1,4,null,null,3,6]
     * 输出：false
     * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
     *
     *
     *
     * 提示：
     *
     *     树中节点数目范围在[1, 104] 内
     *     -231 <= Node.val <= 231 - 1
     */
    Integer pre = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (pre != null && root.val <= pre) return false;
        pre = root.val;
        return isValidBST(root.right);
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     *
     *
     *
     * 示例 1:
     *
     * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 输出: [3,9,20,null,null,15,7]
     *
     * 示例 2:
     *
     * 输入: preorder = [-1], inorder = [-1]
     * 输出: [-1]
     *
     *
     *
     * 提示:
     *
     *     1 <= preorder.length <= 3000
     *     inorder.length == preorder.length
     *     -3000 <= preorder[i], inorder[i] <= 3000
     *     preorder 和 inorder 均 无重复 元素
     *     inorder 均出现在 preorder
     *     preorder 保证 为二叉树的前序遍历序列
     *     inorder 保证 为二叉树的中序遍历序列
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        int m = inorder.length;
        for (int i = 0; i < m; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTree(preorder, inorderMap, 0, m - 1, 0, m - 1);
    }

    private TreeNode buildTree(int[] preorder, Map<Integer, Integer> inorderMap, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        if (preorderLeft > preorderRight) return null;
        //根节点
        int root = preorder[preorderLeft];
        TreeNode treeNode = new TreeNode(root);
        int rootIndex = inorderMap.get(root);
        int leftLength = rootIndex - inorderLeft;
        //左节点
        treeNode.left = buildTree(preorder, inorderMap, preorderLeft + 1, preorderLeft + leftLength, inorderLeft, rootIndex - 1);
        //右节点
        treeNode.right = buildTree(preorder, inorderMap, preorderLeft + 1 + leftLength, preorderRight, rootIndex + 1, inorderRight);
        return treeNode;
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     *
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [-10,-3,0,5,9]
     * 输出：[0,-3,9,-10,null,5]
     * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
     *
     * 示例 2：
     *
     * 输入：nums = [1,3]
     * 输出：[3,1]
     * 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 104
     *     -104 <= nums[i] <= 104
     *     nums 按 严格递增 顺序排列
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) return null;
        int rootIndex = (left + right) / 2;
        TreeNode treeNode = new TreeNode(nums[rootIndex]);
        treeNode.left = sortedArrayToBST(nums, left, rootIndex - 1);
        treeNode.right = sortedArrayToBST(nums, rootIndex + 1, right);
        return treeNode;
    }

    /**
     * 215. 数组中的第K个最大元素
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     *
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     *
     *
     * 示例 1:
     *
     * 输入: [3,2,1,5,6,4], k = 2
     * 输出: 5
     *
     * 示例 2:
     *
     * 输入: [3,2,3,1,2,4,5,5,6], k = 4
     * 输出: 4
     *
     *
     *
     * 提示：
     *
     *     1 <= k <= nums.length <= 105
     *     -104 <= nums[i] <= 104
     */
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums);
        return nums[nums.length - k];
    }

    /**
     * 快速排序
     */
    private void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int low, int high) {
        if (low >= high) return;
        //temp就是基准位
        int i = low, j = high, temp = nums[low];
        while (i < j) {
            while (i < j && nums[j] >= temp) {
                j--;
            }
            while (i < j && nums[i] <= temp) {
                i++;
            }
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        //交换中间位置
        nums[low] = nums[i];
        nums[i] = temp;
        //左侧
        quickSort(nums, low, i - 1);
        //右侧
        quickSort(nums, i + 1, high);
    }

    /**
     * 冒泡排序
     */
    private void bubbleSort(int[] nums) {
        for (int i = 0, length = nums.length; i < length; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                int temp = nums[j];
                if (temp > nums[j + 1]) {
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 35. 搜索插入位置
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * 请必须使用时间复杂度为 O(log n) 的算法。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums = [1,3,5,6], target = 5
     * 输出: 2
     *
     * 示例 2:
     *
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     *
     * 示例 3:
     *
     * 输入: nums = [1,3,5,6], target = 7
     * 输出: 4
     *
     *
     *
     * 提示:
     *
     *     1 <= nums.length <= 104
     *     -104 <= nums[i] <= 104
     *     nums 为 无重复元素 的 升序 排列数组
     *     -104 <= target <= 104
     */
    public int searchInsert(int[] nums, int target) {
        return binarySearchOrInsert(nums, target, 0, nums.length - 1);
    }

    private int binarySearchOrInsert(int[] nums, int target, int left, int right) {
        if (left > right) return left;
        int middle = (left + right) / 2;
        if (nums[middle] == target) return middle;
        if (nums[middle] < target) {
            return binarySearchOrInsert(nums, target, middle + 1, right);
        } else {
            return binarySearchOrInsert(nums, target, left, middle - 1);
        }
    }

    /**
     * 74. 搜索二维矩阵
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     *
     *     每行中的整数从左到右按非严格递增顺序排列。
     *     每行的第一个整数大于前一行的最后一个整数。
     *
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
     * 输出：false
     *
     *
     *
     * 提示：
     *
     *     m == matrix.length
     *     n == matrix[i].length
     *     1 <= m, n <= 100
     *     -104 <= matrix[i][j], target <= 104
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrix(matrix, target, 0, matrix.length - 1);
    }

    private boolean searchMatrix(int[][] matrix, int target, int left, int right) {
        if (left > right) return false;
        int middle = (left + right) / 2;
        int[] middleMatrix = matrix[middle];
        if (target < middleMatrix[0]) {
            return searchMatrix(matrix, target, left, middle - 1);
        } else if (target > middleMatrix[middleMatrix.length - 1]) {
            return searchMatrix(matrix, target, middle + 1, right);
        } else {
            return searchArray(middleMatrix, target, 0, matrix[left].length - 1);
        }
    }

    private boolean searchArray(int[] array, int target, int left, int right) {
        if (left > right) return false;
        int middle = (left + right) / 2;
        if (array[middle] == target) return true;
        if (target < array[middle]) {
            return searchArray(array, target, left, middle - 1);
        } else {
            return searchArray(array, target, middle + 1, right);
        }
    }

    /**
     * 162. 寻找峰值
     * 中等
     * 相关标签
     * 相关企业
     *
     * 峰值元素是指其值严格大于左右相邻值的元素。
     *
     * 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     *
     * 你可以假设 nums[-1] = nums[n] = -∞ 。
     *
     * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,3,1]
     * 输出：2
     * 解释：3 是峰值元素，你的函数应该返回其索引 2。
     *
     * 示例 2：
     *
     * 输入：nums = [1,2,1,3,5,6,4]
     * 输出：1 或 5
     * 解释：你的函数可以返回索引 1，其峰值元素为 2；
     *      或者返回索引 5， 其峰值元素为 6。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 1000
     *     -231 <= nums[i] <= 231 - 1
     *     对于所有有效的 i 都有 nums[i] != nums[i + 1]
     */
    public int findPeakElement(int[] nums) {
        return findPeakElement(nums, 0, nums.length - 1);
    }

    private int findPeakElement(int[] nums, int left, int right) {
        int middle = (left + right) / 2;
        if (middle == left || middle == right) {
            return nums[left] > nums[right] ? left : right;
        }
        int middleNum = nums[middle];
        if (middleNum <= nums[middle - 1]) {
            return findPeakElement(nums, left, middle - 1);
        } else if (middleNum <= nums[middle + 1]) {
            return findPeakElement(nums, middle + 1, right);
        } else {
            return middle;
        }
    }

    /**
     * 33. 搜索旋转排序数组
     * 中等
     * 相关标签
     * 相关企业
     *
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     *
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     *
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     *
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     *
     * 示例 2：
     *
     * 输入：nums = [4,5,6,7,0,1,2], target = 3
     * 输出：-1
     *
     * 示例 3：
     *
     * 输入：nums = [1], target = 0
     * 输出：-1
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 5000
     *     -104 <= nums[i] <= 104
     *     nums 中的每个值都 独一无二
     *     题目数据保证 nums 在预先未知的某个下标上进行了旋转
     *     -104 <= target <= 104
     */
    public int search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }

    private int search(int[] nums, int target, int left, int right) {
        if (left > right) return -1;
        int middle = (left + right) / 2;
        int middleNum = nums[middle];
        if (target == middleNum) return middle;
        //从中间分开后，总有一边是有序的，先找有序的一边，找不到再二分无序的一边
        if (middleNum < nums[0]) { //右边是有序的
            int res = search(nums, target, middle + 1, right);
            if (res != -1) return res;
            return search(nums, target, left, middle - 1);
        } else { //左边是有序的
            int res = search(nums, target, left, middle - 1);
            if (res != -1) return res;
            return search(nums, target, middle + 1, right);
        }
    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     *
     * 示例 2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     *
     * 示例 3：
     *
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     *
     *
     *
     * 提示：
     *
     *     0 <= nums.length <= 105
     *     -109 <= nums[i] <= 109
     *     nums 是一个非递减数组
     *     -109 <= target <= 109
     */
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        searchRange(nums, target, 0, nums.length - 1, res);
        return res;
    }

    private void searchRange(int[] nums, int target, int left, int right, int[] res) {
        if (left > right) return;
        if (res[0] == -1 && nums[left] == target) res[0] = left;
        if (res[1] == -1 && nums[right] == target) res[1] = right;
        if (res[0] != -1 && res[1] != -1) return;
        int mid = (left + right) / 2;
        if (target < nums[mid]) {
            searchRange(nums, target, left, mid - 1, res);
        } else if (target > nums[mid]) {
            searchRange(nums, target, mid + 1, right, res);
        } else {
            if (res[0] == -1) left++;
            if (res[1] == -1) right--;
            searchRange(nums, target, left, right, res);
        }
    }

    /**
     * 153. 寻找旋转排序数组中的最小值
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     *
     *     若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     *     若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     *
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     *
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     *
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [3,4,5,1,2]
     * 输出：1
     * 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
     *
     * 示例 2：
     *
     * 输入：nums = [4,5,6,7,0,1,2]
     * 输出：0
     * 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
     *
     * 示例 3：
     *
     * 输入：nums = [11,13,15,17]
     * 输出：11
     * 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
     *
     *
     *
     * 提示：
     *
     *     n == nums.length
     *     1 <= n <= 5000
     *     -5000 <= nums[i] <= 5000
     *     nums 中的所有整数 互不相同
     *     nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
     */
    public int findMin(int[] nums) {
        return findMin(nums, Integer.MAX_VALUE, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int min, int left, int right) {
        if (left > right) return min;
        int mid = (left + right) / 2;
        int mNum = nums[mid];
        if (mNum < nums[0]) { //右边有序
            return findMin(nums, Math.min(min, mNum), left, mid - 1);
        } else { //左边有序
            return findMin(nums, Math.min(min, nums[left]), mid + 1, right);
        }
    }

    /**
     * 9. 回文数
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     *
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *
     *     例如，121 是回文，而 123 不是。
     *
     *
     *
     * 示例 1：
     *
     * 输入：x = 121
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：x = -121
     * 输出：false
     * 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
     *
     * 示例 3：
     *
     * 输入：x = 10
     * 输出：false
     * 解释：从右向左读, 为 01 。因此它不是一个回文数。
     *
     *
     *
     * 提示：
     *
     *     -231 <= x <= 231 - 1
     *
     *
     *
     * 进阶：你能不将整数转为字符串来解决这个问题吗？
     */
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        if (x < 10) return true;
        if (x % 10 == 0) return false;
        char[] chars = String.valueOf(x).toCharArray();
        for (int i = 0, j = chars.length - 1; i < j; i++, j--) {
            if (chars[i] != chars[j]) return false;
        }
        return true;
    }

    /**
     * 66. 加一
     * 简单
     * 相关标签
     * 相关企业
     *
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     *
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     *
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     *
     *
     * 示例 1：
     *
     * 输入：digits = [1,2,3]
     * 输出：[1,2,4]
     * 解释：输入数组表示数字 123。
     *
     * 示例 2：
     *
     * 输入：digits = [4,3,2,1]
     * 输出：[4,3,2,2]
     * 解释：输入数组表示数字 4321。
     *
     * 示例 3：
     *
     * 输入：digits = [0]
     * 输出：[1]
     *
     *
     *
     * 提示：
     *
     *     1 <= digits.length <= 100
     *     0 <= digits[i] <= 9
     */
    public int[] plusOne(int[] digits) {
        return plus(digits, 1, digits.length - 1);
    }

    private int[] plus(int[] digits, int add, int right) {
        if (right < 0) return digits;
        digits[right] += add;
        if (digits[right] < 10) return digits; //不进位，直接返回
        digits[right] = digits[right] % 10; //进位
        if (right == 0) { //第一位，进位需要复制长度+1的新数组
            int[] res = new int[digits.length + 1];
            res[0] = 1;
            int i = 1;
            for (int digit : digits) {
                res[i] = digit;
                i++;
            }
            return res;
        }
        return plus(digits, 1, --right); //进位后向前处理下一位
    }

    public int[] plusOne1(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            if (digits[i] < 10) return digits;
            digits[i] = 0;
            if (i == 0) {
                digits = new int[digits.length + 1];
                digits[0] = 1;
            }
        }
        return digits;
    }

    /**
     * 69. x 的平方根
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     *
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     *
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：x = 4
     * 输出：2
     *
     * 示例 2：
     *
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     *
     *
     *
     * 提示：
     *
     *     0 <= x <= 231 - 1
     */
    public int mySqrt(int x) { //二分查找法
        int left = 0, right = x, res = -1;
        while (left <= right) {
            int m = (left + right) / 2;
            if ((long) m * m <= x) { //一定要使用long，否则若平方值大于int会变为负数导致一致循环
                res = m;
                left = m + 1;
            } else {
                right = m - 1;
            }
        }
        return res;
    }

    /**
     * 138. 随机链表的复制
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     *
     * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
     *
     * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
     *
     * 返回复制链表的头节点。
     *
     * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
     *
     *     val：一个表示 Node.val 的整数。
     *     random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
     *
     * 你的代码 只 接受原链表的头节点 head 作为传入参数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
     *
     * 示例 2：
     *
     * 输入：head = [[1,1],[2,1]]
     * 输出：[[1,1],[2,1]]
     *
     * 示例 3：
     *
     * 输入：head = [[3,null],[3,0],[3,null]]
     * 输出：[[3,null],[3,0],[3,null]]
     *
     *
     *
     * 提示：
     *
     *     0 <= n <= 1000
     *     -104 <= Node.val <= 104
     *     Node.random 为 null 或指向链表中的节点。
     */
    Map<Node, Node> nodeMap = new HashMap<>(); //next、random可能存在循环引用，保存已遍历过的节点映射关系
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (nodeMap.containsKey(head)) return nodeMap.get(head); //如果节点是循环引用，则直接返回已生成的节点
        Node node = new Node(head.val);
        nodeMap.put(head, node); //保存已遍历过的节点映射关系
        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        return node;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 172. 阶乘后的零
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
     *
     * 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
     *
     *
     *
     * 示例 1：
     *
     * 输入：n = 3
     * 输出：0
     * 解释：3! = 6 ，不含尾随 0
     *
     * 示例 2：
     *
     * 输入：n = 5
     * 输出：1
     * 解释：5! = 120 ，有一个尾随 0
     *
     * 示例 3：
     *
     * 输入：n = 0
     * 输出：0
     *
     *
     *
     * 提示：
     *
     *     0 <= n <= 104
     *
     *
     *
     * 进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
     */
    public int trailingZeroes(int n) {
        // 其中只有2*5末尾才有0，所以就可以抛去其他数据 专门看2 5 以及其倍数 毕竟 4 * 25末尾也是0
        // 2肯定比5多 所以只数5的个数就行了
        int count = 0;
        while (n >= 5) {
            int i = n / 5;
            count += i;
            n = i;
        }
        return count;
    }

    /**
     * 70. 爬楼梯
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     *
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     *
     *
     * 示例 1：
     *
     * 输入：n = 2
     * 输出：2
     * 解释：有两种方法可以爬到楼顶。
     * 1. 1 阶 + 1 阶
     * 2. 2 阶
     *
     * 示例 2：
     *
     * 输入：n = 3
     * 输出：3
     * 解释：有三种方法可以爬到楼顶。
     * 1. 1 阶 + 1 阶 + 1 阶
     * 2. 1 阶 + 2 阶
     * 3. 2 阶 + 1 阶
     *
     *
     *
     * 提示：
     *
     *     1 <= n <= 45
     */
    public int climbStairs(int n) {
        //剩余楼梯，按一次走1阶或2阶
        /**
         * 0: 1
         * 1: 1
         * 2: 1 + 1
         * 3: (1 + 1) + 1
         * 4: ((1 + 1) + 1) + (1 + 1)
         * 5: (((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)
         *
         * 等于前两个台阶之和
         */
        if (n <= 1) return 1;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 我们用 f(x) 表示爬到第 xxx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
     * f(x)=f(x−1)+f(x−2)
     * 它意味着爬到第 xxx 级台阶的方案数是爬到第 x−1x - 1x−1 级台阶的方案数和爬到第 x−2x - 2x−2 级台阶的方案数的和
     */
    public int climbStairs1(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    /**
     * 198. 打家劫舍
     * 中等
     * 相关标签
     * 相关企业
     *
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[1,2,3,1]
     * 输出：4
     * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     *
     * 示例 2：
     *
     * 输入：[2,7,9,3,1]
     * 输出：12
     * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 100
     *     0 <= nums[i] <= 400
     */
    public int rob(int[] nums) {
        return rob(nums, 0);
    }

    private int rob(int[] nums, int from) {
        if (from >= nums.length) return 0;
        if (from == nums.length - 1) return nums[from];
        return Math.max(nums[from] + rob(nums, from + 2), nums[from + 1] + rob(nums, from + 3));
    }

    /**
     * 根据上述递归思路，写出遍历
     * 到每个房子，都有两种偷法，从当前房子开始偷，或者从下一个房子开始偷，取这两种偷法的最大金额
     * 下列代码，优化递归，使用dp[]记录前面已经偷的两种方法的最大值
     */
    public int rob1(int[] nums) {
        int length = nums.length;
        if (length == 0) return 0;
        if (length == 1) return nums[0];
        int[] dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(nums[i] + (i < 2 ? 0 : dp[i - 2]), nums[i - 1] + (i < 3 ? 0 : dp[i - 3]));
        }
        return dp[length - 1];
    }

    /**
     * 139. 单词拆分
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
     *
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     *
     *
     *
     * 示例 1：
     *
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
     *
     * 示例 2：
     *
     * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * 输出: true
     * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     *      注意，你可以重复使用字典中的单词。
     *
     * 示例 3：
     *
     * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * 输出: false
     *
     *
     *
     * 提示：
     *
     *     1 <= s.length <= 300
     *     1 <= wordDict.length <= 1000
     *     1 <= wordDict[i].length <= 20
     *     s 和 wordDict[i] 仅由小写英文字母组成
     *     wordDict 中的所有字符串 互不相同
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s.length() == 0) return true;
        for (String word : wordDict) {
            if (s.startsWith(word) && wordBreak(s.replaceFirst(word, ""), wordDict)) {
                return true;
            }
        }
        return false;
    }

    public boolean wordBreak1(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                //如果 [0, j] 字符可以拼出，且 [j, i] 也可以拼出，则 dp[i] 整个可以拼出
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true; //记录每个 [0, i] 的字符可以拼出，否则默认false
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 148. 排序链表
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     *
     * 示例 2：
     *
     * 输入：head = [-1,5,3,4,0]
     * 输出：[-1,0,3,4,5]
     *
     * 示例 3：
     *
     * 输入：head = []
     * 输出：[]
     *
     *
     *
     * 提示：
     *
     *     链表中节点的数目在范围 [0, 5 * 104] 内
     *     -105 <= Node.val <= 105
     *
     *
     *
     * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    private ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) return null;
        if (head.next == tail) {
            head.next = null; //结尾点不用，只判断是否到结尾
            return head;
        }
        //二分归并，先分成两个链表，排序单个链表，再将两个有序链表合并
        //快慢指针找中间点
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next; //取中间或偏向后边的节点
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode list1 = sortList(head, slow); //结尾点不用，只判断是否到结尾
        ListNode list2 = sortList(slow, tail);
        //合并两个有序列表为一个有序链表
        return merge(list1, list2);
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        } else {
            list2.next = merge(list2.next, list1);
            return list2;
        }
    }

    private ListNode merge1(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode temp = head;
        while (list1 != null || list2 != null) {
            if (list1 == null) {
                temp.next = list2;
                break;
            }
            if (list2 == null) {
                temp.next = list1;
                break;
            }
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        return head.next;
    }

    public ListNode merge2(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }

    /**
     * 427. 建立四叉树
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
     *
     * 你需要返回能表示矩阵 grid 的 四叉树 的根结点。
     *
     * 四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
     *
     *     val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
     *     isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
     *
     * class Node {
     *     public boolean val;
     *     public boolean isLeaf;
     *     public Node topLeft;
     *     public Node topRight;
     *     public Node bottomLeft;
     *     public Node bottomRight;
     * }
     *
     * 我们可以按以下步骤为二维区域构建四叉树：
     *
     *     如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
     *     如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
     *     使用适当的子网格递归每个子节点。
     *
     * 如果你想了解更多关于四叉树的内容，可以参考 wiki 。
     *
     * 四叉树格式：
     *
     * 你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
     *
     * 它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
     *
     * 如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：grid = [[0,1],[1,0]]
     * 输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
     * 解释：此示例的解释如下：
     * 请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。
     *
     * 示例 2：
     *
     * 输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
     * 输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
     * 解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
     * topLeft，bottomLeft 和 bottomRight 均具有相同的值。
     * topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
     * 解释如下图所示：
     *
     *
     *
     * 提示：
     *
     *     n == grid.length == grid[i].length
     *     n == 2x 其中 0 <= x <= 6
     */
    @Getter
    static class QuadNode {
        public boolean val;
        public boolean isLeaf;
        public QuadNode topLeft;
        public QuadNode topRight;
        public QuadNode bottomLeft;
        public QuadNode bottomRight;

        public QuadNode() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public QuadNode(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public QuadNode(boolean val, boolean isLeaf, QuadNode topLeft, QuadNode topRight, QuadNode bottomLeft, QuadNode bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

    public QuadNode construct(int[][] grid) {
        return construct(grid, 0, grid.length - 1, 0, grid.length - 1);
    }

    private QuadNode construct(int[][] grid, int left, int right, int top, int bottom) {
        if (left > right || top > bottom) return null;
        int x = grid[top][left];
        int i = left, j = top;
        while (i <= right && j <= bottom) {
            if (grid[j][i] != x) {
                //有值不等，非叶子节点，继续往下四分
                return new QuadNode(
                        false, false,
                        construct(grid, left, (left + right) / 2, top, (top + bottom) / 2),
                        construct(grid, (left + right) / 2 + 1, right, top, (top + bottom) / 2),
                        construct(grid, left, (left + right) / 2, (top + bottom) / 2 + 1, bottom),
                        construct(grid, (left + right) / 2 + 1, right, (top + bottom) / 2 + 1, bottom)
                );
            }
            if (i == right) { //换行
                i = left;
                j++;
            } else { //下一列
                i++;
            }
        }
        return new QuadNode(x == 1, true);
    }

    /**
     * 23. 合并 K 个升序链表
     * 困难
     * 相关标签
     * 相关企业
     *
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     *
     *
     * 示例 1：
     *
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     *
     * 示例 2：
     *
     * 输入：lists = []
     * 输出：[]
     *
     * 示例 3：
     *
     * 输入：lists = [[]]
     * 输出：[]
     *
     *
     *
     * 提示：
     *
     *     k == lists.length
     *     0 <= k <= 10^4
     *     0 <= lists[i].length <= 500
     *     -10^4 <= lists[i][j] <= 10^4
     *     lists[i] 按 升序 排列
     *     lists[i].length 的总和不超过 10^4
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeKLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeKLists(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        return merge(mergeKLists(lists, left, (left + right) / 2), mergeKLists(lists, (left + right) / 2 + 1, right));
    }

    /**
     * 80. 删除有序数组中的重复项 II
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     *
     *
     * 说明：
     *
     * 为什么返回数值是整数，但输出的答案是数组呢？
     *
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     *
     * 你可以想象内部操作如下:
     *
     * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
     * int len = removeDuplicates(nums);
     *
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,1,2,2,3]
     * 输出：5, nums = [1,1,2,2,3]
     * 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
     *
     * 示例 2：
     *
     * 输入：nums = [0,0,1,1,1,1,2,3,3]
     * 输出：7, nums = [0,0,1,1,2,3,3]
     * 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 3 * 104
     *     -104 <= nums[i] <= 104
     *     nums 已按升序排列
     */
    public int removeDuplicates1(int[] nums) {
        int length = nums.length;
        if (length <= 2) return length;
        int i = length - 1, j = i, k = i, n = 0;
        while (i >= 0) {
            if (nums[i] == nums[j] && j - i >= 2) {
                nums[i] = nums[k];
                k--; //末尾可替换指针
                n++; //记录删除的个数
            } else if (nums[i] != nums[j]) {
                j = i;
            }
            i--; //最前的指针，j是当前与最前相同的最后指针，记录相同个数
        }
        length = length - n;
        //排序
        quickSort(nums, 0, length - 1);
        return length;
    }

    public int removeDuplicates2(int[] nums) {
        int length = nums.length;
        if (length <= 2) return length;
        int slow = 2, fast = 2;
        while (fast < length) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    /**
     * 189. 轮转数组
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右轮转 1 步: [7,1,2,3,4,5,6]
     * 向右轮转 2 步: [6,7,1,2,3,4,5]
     * 向右轮转 3 步: [5,6,7,1,2,3,4]
     *
     * 示例 2:
     *
     * 输入：nums = [-1,-100,3,99], k = 2
     * 输出：[3,99,-1,-100]
     * 解释:
     * 向右轮转 1 步: [99,-1,-100,3]
     * 向右轮转 2 步: [3,99,-1,-100]
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 105
     *     -231 <= nums[i] <= 231 - 1
     *     0 <= k <= 105
     *
     *
     *
     * 进阶：
     *
     *     尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
     *     你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
     */
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        if (length <= 1 || k == length) return;
        if (k > length) k = k % length;
        rotate(nums, k, 0);
    }

    private void rotate(int[] nums, int k, int i) {
        if (i == k) return;
        int length = nums.length;
        int last = nums[length - 1];
        for (int j = length - 1; j > 0; j--) {
            nums[j] = nums[j - 1];
        }
        nums[0] = last;
        rotate(nums, k, ++i);
    }

    public void rotate1(int[] nums, int k) {
        int length = nums.length;
        if (length <= 1 || k == length) return;
        if (k > length) k = k % length;
        int[] temp = new int[k];
        for (int i = length - k, j = 0; i < length; i++, j++) {
            temp[j] = nums[i];
        }
        for (int i = length - 1, j = length - k; j > 0; i--, j--) {
            nums[i] = nums[i - k];
        }
        for (int i = 0; i < k; i++) {
            nums[i] = temp[i];
        }
    }

    /**
     * 55. 跳跃游戏
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [2,3,1,1,4]
     * 输出：true
     * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
     *
     * 示例 2：
     *
     * 输入：nums = [3,2,1,0,4]
     * 输出：false
     * 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
     *
     *
     *
     * 提示：
     *
     *     1 <= nums.length <= 104
     *     0 <= nums[i] <= 105
     */
    public boolean canJump(int[] nums) {
        //从后往前数，判断当前位置能否由前面的位置跳到
        int length = nums.length;
        if (length == 1) return true;
        int i = length - 1, j = length - 2;
        while (j >= 0) {
             if (i - j <= nums[j]) {
                 i = j;
             }
             j--;
        }
        return i <= nums[0];
    }

    /**
     * 45. 跳跃游戏 II
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     *
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     *
     *     0 <= j <= nums[i]
     *     i + j < n
     *
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums = [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     *
     * 示例 2:
     *
     * 输入: nums = [2,3,0,1,4]
     * 输出: 2
     *
     *
     *
     * 提示:
     *
     *     1 <= nums.length <= 104
     *     0 <= nums[i] <= 1000
     *     题目保证可以到达 nums[n-1]
     */
    public int jump(int[] nums) {
        // 记录当前能跳跃到的位置的边界下标
        int border = 0;
        // 记录在边界范围内，能跳跃的最远位置的下标
        int maxPosition = 0;
        // 记录所用步数
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            // 继续往下遍历，统计边界范围内，哪一格能跳得更远，每走一步就更新一次能跳跃的最远位置下标
            // 其实就是在统计下一步的最优情况
            maxPosition = Math.max(maxPosition, i + nums[i]);
            // 如果到达了边界，那么一定要跳了，下一跳的边界下标就是之前统计的最优情况maxPosition，并且步数加1
            if (i == border) {
                border = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    /**
     * 274. H 指数
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     *
     * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
     *
     * 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
     *
     *
     *
     * 示例 1：
     *
     * 输入：citations = [3,0,6,1,5]
     * 输出：3
     * 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     *      由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
     *
     * 示例 2：
     *
     * 输入：citations = [1,3,1]
     * 输出：1
     *
     *
     *
     * 提示：
     *
     *     n == citations.length
     *     1 <= n <= 5000
     *     0 <= citations[i] <= 1000
     */
    public int hIndex(int[] citations) {
        int length = citations.length;
        sort(citations, 0, length - 1);
        int j = 0, m = 0;
        for (int i = length - 1; i >= 0 && citations[i] >= j; i--, j++) {
            m = citations[i];
        }
        return Math.min(j, m);
    }

    private void sort(int[] array, int left, int right) {
        if (left >= right) return;
        int t = array[left], x = left, y = right;
        while (x < y) {
            while (x < y && array[y] >= t) {
                y--;
            }
            while (x < y && array[x] <= t) {
                x++;
            }
            if (x < y) {
                int temp = array[x];
                array[x] = array[y];
                array[y] = temp;
            }
        }
        array[left] = array[x];
        array[x] = t;
        sort(array, left, x - 1);
        sort(array, x + 1, right);
    }

    /**
     * 380. O(1) 时间插入、删除和获取随机元素
     * 中等
     * 相关标签
     * 相关企业
     *
     * 实现RandomizedSet 类：
     *
     *     RandomizedSet() 初始化 RandomizedSet 对象
     *     bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
     *     bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
     *     int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
     *
     * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
     *
     *
     *
     * 示例：
     *
     * 输入
     * ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
     * [[], [1], [2], [2], [], [1], [2], []]
     * 输出
     * [null, true, false, true, 2, true, false, 2]
     *
     * 解释
     * RandomizedSet randomizedSet = new RandomizedSet();
     * randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
     * randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
     * randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
     * randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
     * randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
     * randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
     * randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
     *
     *
     *
     * 提示：
     *
     *     -231 <= val <= 231 - 1
     *     最多调用 insert、remove 和 getRandom 函数 2 * 105 次
     *     在调用 getRandom 方法时，数据结构中 至少存在一个 元素。
     */
    static class RandomizedSet {
        List<Integer> list;
        Map<Integer, Integer> map;
        Random random;

        public RandomizedSet() {
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) return false;
            int i = list.size();
            list.add(val);
            map.put(val, i);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) return false;
            int i = map.remove(val);
            int size = list.size();
            if (i != size - 1) { //如果不是删除最后一个元素，会导致删除元素后面元素的位置变更
                int last = list.get(size - 1);
                list.set(i, last); //将最后一个元素替换到要删除的位置
                map.put(last, i); //更新map中变更的最后一个元素的位置关系
            }
            list.remove(size - 1); //删除最后一个元素
            return true;
        }

        public int getRandom() {
            int i = random.nextInt(list.size());
            return list.get(i);
        }
    }

    /**
     * 238. 除自身以外数组的乘积
     * 中等
     * 相关标签
     * 相关企业
     *
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     *
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     *
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums = [1,2,3,4]
     * 输出: [24,12,8,6]
     *
     * 示例 2:
     *
     * 输入: nums = [-1,1,0,-3,3]
     * 输出: [0,0,9,0,0]
     *
     *
     *
     * 提示：
     *
     *     2 <= nums.length <= 105
     *     -30 <= nums[i] <= 30
     *     保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
     *
     *
     *
     * 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
     */
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] left = new int[length];
        int[] right = new int[length];

        left[0] = 1;
        for (int i = 1; i < length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        right[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < length; i++) {
            nums[i] = left[i] * right[i];
        }
        return nums;
    }

    /**
     * 134. 加油站
     * 中等
     * 相关标签
     * 相关企业
     *
     * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
     *
     * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
     *
     * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
     *
     *
     *
     * 示例 1:
     *
     * 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
     * 输出: 3
     * 解释:
     * 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
     * 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
     * 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
     * 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
     * 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
     * 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
     * 因此，3 可为起始索引。
     *
     * 示例 2:
     *
     * 输入: gas = [2,3,4], cost = [3,4,3]
     * 输出: -1
     * 解释:
     * 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
     * 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
     * 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
     * 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
     * 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
     * 因此，无论怎样，你都不可能绕环路行驶一周。
     *
     *
     *
     * 提示:
     *
     *     gas.length == n
     *     cost.length == n
     *     1 <= n <= 105
     *     0 <= gas[i], cost[i] <= 104
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int j = 0;
            int cnt = 0;
            while (j < n) {
                int x = (j + i) % n;
                cnt += gas[x] - cost[x];
                if (cnt < 0) {
                    i += j;
                    break;
                }
                j++;
            }
            if (j == n) {
                return i;
            }
            i++;
        }
        return -1;
    }

    /**
     * 12. 整数转罗马数字
     * 中等
     * 相关标签
     * 相关企业
     *
     * 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
     *
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     *
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     *
     *     I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     *     X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
     *     C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     *
     * 给你一个整数，将其转为罗马数字。
     *
     *
     *
     * 示例 1:
     *
     * 输入: num = 3
     * 输出: "III"
     *
     * 示例 2:
     *
     * 输入: num = 4
     * 输出: "IV"
     *
     * 示例 3:
     *
     * 输入: num = 9
     * 输出: "IX"
     *
     * 示例 4:
     *
     * 输入: num = 58
     * 输出: "LVIII"
     * 解释: L = 50, V = 5, III = 3.
     *
     * 示例 5:
     *
     * 输入: num = 1994
     * 输出: "MCMXCIV"
     * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
     *
     *
     *
     * 提示：
     *
     *     1 <= num <= 3999
     */
    public String intToRoman(int num) {
//        StringBuilder builder = new StringBuilder();
//        int x = 1;
//        while (num > 0) {
//            x *= 10;
//            int i = num % x;
//            if (i > 0 && i < 4) {
//                for (int j = 0; j < i; j++) {
//                    builder.app
//                }
//            }
//        }
        return "";
    }
}
